package dujiu.leetcode.graph;


public class P547 {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;// 城市数量
        boolean[] flag = new boolean[n+1]; // 标记城市是否被访问过
        int count = 0; // 记录连接块（省份）的数量

        for (int i = 0; i <= n; i++) { //遍历每一个城市
            if (!flag[i]){ // 说明没有被访问过
                flag[i] = true;
                count++;
                dfs(isConnected,flag,i);
            }
        }
        return count;
    }

    public void dfs(int[][] isConnected, boolean[] flag, int i){
        for (int j = 0; j < isConnected[i].length; j++) {
            if (j != i && isConnected[i][j] == 1 && !flag[j]){
                flag[j] = true;
                dfs(isConnected,flag,j);
            }
        }
    }
}
